<!DOCTYPE html>
<html lang="en">

<head>
    <meta charset="UTF-8">
    <meta http-equiv="X-UA-Compatible" content="IE=edge">
    <meta name="viewport" content="width=device-width, initial-scale=1.0">
    <title>Document</title>
</head>

<body>
    <script>
        //小于基准数字的元素放左边，大于的放右边
        //时间复杂度：平均O(nlogn)，最坏O(n2)，实际上大多数情况下小于O(nlogn) 空间复杂度:O(logn)（递归调用消耗） 
        //稳定性：不稳定，无法保证相等的元素的相对位置不变
        function quickSort(array) {
            if (array.length < 2) {
                return array;
            }
            const mid = array[0];
            const left = [];
            const right = [];
            for (let i = 1; i < array.length; i++) {
                if (array[i] < mid) {
                    left.push(array[i]);
                } else {
                    right.push(array[i]);
                }
            }
            return [...quickSort(left), mid, ...quickSort(right)];
        }
        const arr = [5, 5, 7, 2, 8, 1, 0, 4, 5, 1];
        console.log(quickSort(arr));
    </script>
</body>

</html>